Lambda the Ultimate

O'Reilly is hosting a collaborative book/wiki called Software Craftsmanship: Apprentice to Journeyman. It's structured as a series of "recipes" on how to approach different aspects of software development.

I am glad to see many new members joining the LtU daily.

This is a short reminder to all the new users to please read the FAQ and policy documents, and use LtU for the intended purposes of the site (the LtU spirit page may also be of interest). As the community gets larger it becomes more important to keep in mind the shared interests that bring most people to the site.

I also recommend reading the getting start thread (linked from the FAQ), which contains many useful reading suggestions, as well as the various other pages linked to from the navigation bar on the left.

As always old time members are urged to assist the newer members and make them feel welcome to our community.

When Is A Functional Program Not A Functional Program?, John Longley. ICFP 1999.

In an impure functional language, there are programs whose behavior is completely functional (in that they behave extensionally on inputs) but the functions they compute cannot be written in the purely functional fragment of the language. That is, the class of programs with functional behavior is more expressive than the usual class of pure functional programs. In this paper we introduce this extended class of "functional" programs by means of examples in Standard ML, and explore what they might have to offer to programmers and language implementors.

After reviewing some theoretical background, we present some examples of functions of the above kind, and discuss how they may be implemented. We then consider two possible programming applications for these functions: the implementation of a search algorithm, and an algorithm for exact real-number integration. We discuss the advantages and limitations of this style of programming relative to other approaches. We also consider the increased scope for compiler optimizations that these functions would offer.

I like this paper because it shows how some of the most abstract bits of formal logic (realizability models of higher order logic) suggest actual programs you can write.

As a barely-related aside, even a brief look into this realizability stuff also taught me a good deal of humility -- for example, it seems that at higher types, what you can represent mathematically depends on the specific notion of computation you're using. So the mathematical consequences of the Church-Turing thesis are rather more subtle than we might initially expect. (Andrej Bauer discusses a related point in more detail in this blog post.)

From the introduction:

Seen in outline, the history of LC and CL splits into three main periods: first, several years of intensive and very fruitful study in the 1920s and ’30s; next, a middle period of nearly 30 years of relative quiet; then in the late 1960s an upsurge of activity stimulated by developments in higher-order function theory, by connections with programming languages, and by new technical discoveries. The fruits of the first period included the first-ever proof that predicate logic is undecidable. The results of the second attracted very little non-specialist interest, but included completeness, cut-elimination and standardization theorems (for example) that found many uses later. The achievements of the third, from the 1960s onward, included constructions and analyses of models, development of polymorphic type systems, deep analyses of the reduction process, and many others probably well known to the reader. The high level of activity of this period continues today.

Beware: This is a long paper (but less than you might expect it to be by looking at the page count: about half the pages are dedicated to the bibliography).

In the announcement on the TYPES Forum the authors invited comments, suggestions and additional information on the topics of the paper, namely the development of lambda-calculi and combinatory logic from the prehistory (Frege, Peano and Russell) to the end of 20th century.

Nothing terribly exciting or newsworthy, but I suspect that many readers will find something to love in this blog post from Gilad Bracha. He starts by asking, "Why is static state so bad, you ask?" and goes from there...

Given all these downsides, surely there must be some significant upside, something to trade off against the host of evils mentioned above? Well, not really. It’s just a mistake, hallowed by long tradition... Static state will disappear from modern programming languages, and should be eliminated from modern programming practice.

The little b project is an effort to provide an open source language which allows scientists to build mathematical models of complex systems. The initial focus is systems biology. The goal is to stimulate widespread sharing and reuse of models.

The little b language is designed to allow biologists to build models quickly and easily from shared parts, and to allow theorists to program new ways of describing complex systems. Currently, libraries have been developed for building ODE models of molecular networks in multi-compartment systems such as cellular epithelia.

Little b is based in Common Lisp and contains mechanisms for rule-based reasoning, symbolic mathematics and object-oriented definitions. The syntax is designed to be terse and human-readable to facilitate communication. The environment is both interactive and compilable.

Yet another biological DSL.

As usual, it is best to start by looking at some sample models.

Internet, December 16, 2007—The Revised Maclisp Manual, originally published in hardcopy at MIT in 1983 as the Saturday Evening Edition, is now available on the web as the Sunday Morning Edition.

Nicknamed The Pitmanual, The Revised Maclisp Manual describes the programming language MACLISP, which ran on the DEC PDP-10 and Honeywell 6180/6880. This newly-updated Sunday Morning Edition features many editorial corrections, an enhanced hypertext index, and a Common Lisp Conversion guide that offers advice on upgrading old MACLISP programs to run in Common Lisp.

By Kent Pitman, who also brought us the Common Lisp HyperSpec, the very definition of class.

I'm usually a lurker here, but I thought LtU readers might be interested in a post on my blog, looking back on 10 years of my book Purely Functional Data Structures (published in 1998).

You can get soup in a can. You can get bread in a can. Now the long wait is over! You can finally get Lambda Calculus in a can...Project LambdaCan takes [the Lambda Calculus] and implements it on a microcontroller better suited to the most mundane of tasks, like running a vending machine or microwave oven. And it sticks the microcontroller in a can that you can connect to your PC using a USB cable.

For those that are both language geeks and hardware geeks...

Jumbala : An Action Language for UML State Machines, Juro Dubrovin, Master's Thesis.

UML 2.0 is a language for modeling complex software systems. A UML model may describe the dynamic aspects of software as well as the static structure. We concentrate on models of reactive systems, such as embedded controllers or telecommunications switches. The behavior of such systems is modeled using UML state machines. Although UML defines the structure of state machines, it leaves open the choice of an action language,which is the language used to specify how the transitions of a state machine affect the configuration of the underlying model.

A UML action language named Jumbala is introduced. The language has been designed as part of a project where the goal is to formally analyze behavioral UML models. Jumbala is based on the Java programming language. It has nearly the same syntax and semantics for statements and expressions as Java. Some new programming constructs have been added to facilitate state machine modeling. Jumbala also supports object-oriented programming with classes and inheritance.

An interpreter that parses and executes Jumbala programs has been developed. The interpreter will be part of a prototype tool set for analyzing the behavior of reactive computer systems modeled in UML.

This is interesting because it is another example of efforts from the modeling community towards combining models and programming languages to provide a single compilable specification of software. Some of these efforts are being coordinated using the term model-driven architecture (MDA).

[edit: fixed formatting issues]